1. Field of the Invention
The present invention generally relates to object oriented programming (OOP) systems and, more particularly, to OOP systems (such as the Java(trademark) and, C++programming language) that support interfaces.
2. Background Description
An interface specifies a set of methods that must be implemented by any class of objects that declares to implement the interface, but an interface does not provide any implementation of these methods themselves. The Java(trademark) programming model includes such a mechanism. More specifically, a Java(trademark) interface is a public class that includes (among other things) one or more abstract method declarations that provides the method signatures for a set of methods. Any class that declares to implement a given interface (denoted xe2x80x9cinterface classxe2x80x9d) must provide an implementation of the methods specified by the given interface. In Java(trademark), such a class must provide an implementation of the methods specified by the given interface that match the methods signatures specified by the given interface. Note that here a method signature represents the name of a method, the types of its parameters, and its return type. This differs from normal Java(trademark) usage (which does not include the return type). In addition, a given interface may extend (directly or indirectly) another interface. The C++programming model introduced by Microsoft Corporation is another example of a model that supports interfaces.
In OO systems that support interfaces (such as Java(trademark)), a field name (or local variable name) whose type is an interface may reference the objects of any interface class that implements the interface. Moreover, the method of an interface class implemented by a given object (which we denote xe2x80x9cinterface methodxe2x80x9d for the sake of description) may be called by applying the method name (with arguments) to a field name (or local variable name) that points to the given object. Compilation (or interpretation) of such a method invocation statement typically involves generating a routine that performs dynamic dispatch to the called interface method. A more detailed description of Java(trademark) interfaces can be found in U.S. Pat. No. 5,907,707, commonly assigned to the assignee of the present invention, herein incorporated by reference in its entirety.
Efficient implementation of dynamic dispatch of interface methods is difficult because the virtual methods of different classes that match a particular interface method signature may occur in different offsets in the virtual method tables (VMTs) for the different classes. FIG. 1 illustrates this point where the pointer to the method bar ( ) is in the second entry in the VMT for class A but is in the fourth entry of class C""s VMT.(class C implements virtual methods rim and ged; as well as, foo and bar.)
The schemes to identify the correct entry in the VMT typically revolve around keeping a table (which we denote as itable for the sake of description) for each class and for each interface implemented by the class. This table is a virtual method table for the class restricted to methods for a given interface. To dispatch an interface method, the itable is located and a pointer to the target method body is obtained at a fixed offset within it. Sometimes, a dispatch time search for the itable of a required interface for a given class may be required to determine the address of the implementation of the called method. A more detailed description of such schemes can be found in Fitzgerald et al., xe2x80x9cMarmot: An optimizing compiler for Java,xe2x80x9d Technical Report 33, Microsoft Research, Jun. 1999; Ramalingam and Srinivasan, xe2x80x9cObject Model for Java,xe2x80x9d Technical Report 20642, IBM Research Division, Dec. 1996. The principal drawback to these schemes is that the dispatch time search is inefficient and leads to a dispatch mechanism that is computationally more expensive than virtual method dispatch.
In some Java(trademark) implementations, this dispatch time search is optimized for under certain circumstancesxe2x80x94when a sequence of instructions containing a method invocation is executed multiple times. In these cases, the method being invoked in the method table can be cached and this cached value can be used to reduce the overhead of the search (xe2x80x9cThe Java Virtual Machine Specificationxe2x80x9d, by Tim Lindholm and Frank Yellin; xe2x80x9cMethod and Apparatus for Resolving Data References in Generated Codexe2x80x9d, U.S. Pat. No. 5,367,685 in the name of James Gosling. However, these optimization schemes cannot always completely eliminate the dispatch time search when an interface is implemented by multiple classes, and thus suffer from poor performance when invoking interface methods.
Krall and Grafl, xe2x80x9cCACAOxe2x80x94a 64 bit Java VM just-in-time compiler,xe2x80x9d Concurrency: Practice and Experience, 9(11), pp. 1017-1030, 1997, describe two schemes for implementing interface method dispatch. The first scheme is a variant of the itable schemes described above. CACAO maintains an interface table with each class. There is (logically) an entry in this interface table for every interface the system has seen (as the time the class is loaded). Thus, the interface table is typically very large and consumes a large amount of storage. The entry for an interface is empty unless the class implements the interface, in which case it contains the appropriate itable. To dispatch an interface method on an object, the interface table is located, the itable for the interface is loaded at a constant offset, and a pointer to the code for the method is obtained at a constant offset into the itable. In this first scheme, an interface method dispatch is one dependent load more expensive than a virtual method dispatch. Thus, the principal drawback to this first scheme is twofold: i) the interface table typically consumes a large amount of storage, and ii) the dispatch time search is inefficient in that it requires an additional load operation than virtual method dispatch.
It appears the a substantial part of the motivation for CACAO ""s second scheme is a desire to eliminate this extra dependent load operation. In this second scheme, the interface table and itable are collapsed into a single table (denoted the interface-method table) for a class. This interface-method table has (logically) an entry for every interface-method signature in the interface-method table has (logically) an entry for every interface-method signature in the system. This entry points directly at the body of the method that that implements the signature if the class has one (otherwise it is empty). For this scheme, an interface method dispatch has exactly the same cost as a virtual method dispatch. However, the drawback of this second scheme is that the interface-method table will be very big and very sparsely populated. A technique similar to graph-coloring register allocation (see Chaitin et al., xe2x80x9cRegister Allocation via coloring,xe2x80x9d Computer Languages 6, pgs. 47-57, January 1981) can be used to reduce the size of these tables substantially. More specifically, if two interface method signatures are never implemented by the same class, then they can be assigned the same slot in the interface method tables. However, the drawback to this interface-method coloring scheme is that it requires knowledge of all the interfaces the system will ever see in order to do the coloring. Thus, it is not appropriate in a context, such as the Java programming model, that requires dynamic class loading.
Therefore, there remains a need in the art to provide an efficient mechanism for interface method dispatch that reduces the space and computational overhead associated with the dispatch time processing.
The above-stated problems and related problems of the prior art are solved with the principles of the present invention, method and apparatus for efficient interface method dispatch, which includes an interface method table (IMT) for a given class of objects. The IMT comprises a table of entries each corresponding to a set S of interface methods that are implemented by objects of the given class. An IMT entry preferably stores data representing the following:
in the event that the set S is empty, the IMT entry stores a null/empty value;
in the event that the set S includes only a single interface method, the IMT entry stores a pointer to the implementation of the single interface method in the set S; and
in the event that the set S includes two or more interface methods, the IMT entry stores a pointer to a conflict resolution routine.
The entries of the IMT are used to support invocation of interface methods. More specifically, processing of a method invocation statement involves either i) loading the pointer to the implementation of the interface method from an entry of the IMT and passing control to this implementation; or ii) loading the pointer to a conflict resolution routine pointed to by an IMT entry and passing control to this conflict resolution routine. The conflict resolution routine pointed to by the IMT entry identifies (at execution time) the location of the particular interface method (of the two or more interface methods that are associated with the given IMT entry) that corresponds to the method invocation statement being processed, and passes control to this particular interface method. Thus, the interface method invocation mechanism of the present invention advantageously replaces the intensive search performed by prior art techniques with efficient processing that, in the case that the corresponding IMT entry is associated with a single interface method, is equivalent to a virtual method call, or, in the case that the corresponding IMT entry is associated with multiple interface methods, involves lightweight and more efficient conflict resolution code.